package ua.mykola.sorting;

public class MergeSort implements Sorter {

	public void sort(Object[] array) {
		if (array.length == 0)
			return;
		Object[] sorted = mergeSort(array, 0, array.length - 1);
		for (int i = 0; i < sorted.length; i++) {
			array[i] = sorted[i];
		}

	}

	private Object[] mergeSort(Object[] array, int start, int end) {
		if (end - start == 0) {
			return new Object[] { array[start] };
		} else {
			int splitIndex = (end - start) / 2 + start;
			return merge(mergeSort(array, start, splitIndex),
					mergeSort(array, splitIndex + 1, end));
		}
	}

	private Object[] merge(Object[] array1, Object[] array2) {
		Object[] result = new Object[array1.length + array2.length];
		int i = 0;
		int j = 0;
		int r = 0;
		while (i < array1.length && j < array2.length) {
			if (((Comparable) array1[i]).compareTo(array2[j]) < 0) {
				result[r] = array1[i];
				i++;
			} else {
				result[r] = array2[j];
				j++;
			}
			r++;
		}
		if (i == array1.length) {
			for (; j < array2.length; j++) {
				result[r] = array2[j];
				r++;
			}
		} else if (j == array2.length) {
			for (; i < array1.length; i++) {
				result[r] = array1[i];
				r++;
			}
		}
		return result;
	}
}
